#include<vector>
using namespace std;

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        int sum = 0;
        if (grid.size()==0)return sum;
        vector<vector<int>> dp(grid.size(), vector<int>(grid[0].size(),0));
        dp[0][0] = grid[0][0];
        sum = grid[0][0];

        for(int i=1; i<grid.size();i++){
            dp[i][0] = grid[i][0] + dp[i-1][0];
            sum = max(sum, dp[i][0]);
        }

        for(int i=1; i<grid[0].size();i++){
            dp[0][i] = grid[0][i] + dp[0][i-1];
            sum = max(sum, dp[0][i]);
        }

        for (int i = 1; i < grid.size(); i++)
        {
            for (int j = 1; j < grid[0].size(); j++)
            {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
                sum = max(dp[i][j], sum);
            }
            
        }
        
        return sum;
    }
};